// easy

// 给定一个单链表的头节点head
// 要求，将该单链表进行反转，可以迭代或者递归地反转链表

const { ListNode, LinkedList } = require('../../1. 链表基础/1. 建立线性链表')

// —————————————————————迭代———————————————————————
// 时间复杂度：O(n)
// 空间复杂度：O(1)
function reverseList(head) {
    let pre = null
    let cur = head
    // 1 -> 2 -> 3 -> 4
    // 4 -> 3 -> 2 -> 1
    // cur = 1, pre = null, next = 2, 
    // next = cur.next 2
    // cur.next = pre
    // pre = cur
    // cur = next
    while (cur !== null) {
        let next = cur.next 
        cur.next = pre
        pre = cur
        cur = next
    }
    return pre
}

let node = new LinkedList([1, 2, 3, 4])
console.log(reverseList(node.head));

// —————————————————————递归———————————————————————
// 首先定义递归函数含义为：将链表反转，并返回反转后的头节点。
// 在每次递归函数返回的 过程中，改变head和head.next的指向关系
// 时间复杂度：O(n)
// 空间复杂度：O(n)，最多需要n层栈空间

function reverseList2(head) {
    if (head === null || head.next === null) {
        return head
    }
    let new_head = reverseList2(head.next)
    // cur 1 -> cur.next 2
    // cur.next.next = cur
    // cur.next = null
    head.next.next = head
    head.next = null
    return new_head
}

let node2 = new LinkedList([1, 2, 3, 4])
console.log(reverseList2(node2.head))
